package com.itheima.datastructure.demo1;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 计算二叉树的最小深度
 */
public class TreeDeep {

    /**
     * 主函数，用于创建二叉树并调用计算最小深度的方法
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        // 创建二叉树节点
        TreeNode node7 = new TreeNode(7, null, null);
        TreeNode node6 = new TreeNode(6, node7, null);
        TreeNode node5 = new TreeNode(5, null, null);
        TreeNode node4 = new TreeNode(4, null, null);
        TreeNode node3 = new TreeNode(3, node6, null);
        TreeNode node2 = new TreeNode(2, node4, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);
        // 输出最小深度
        System.out.println(minDepth(node1));
        System.out.println(minDepth1(node1));
    }

    /**
     * 计算二叉树的最小深度
     * @param root 二叉树的根节点
     * @return 返回二叉树的最小深度
     */
    public static int minDepth(TreeNode root) {
        // 如果根节点为空，返回 0
        if (root == null) {
            return 0;
        }
        // 如果左右子节点都为空，说明已经到达叶子节点，返回 1
        if (root.left == null && root.right == null) {
            return 1;
        }
        // 计算左子树的最小深度，如果左子节点为空，则赋值为最大整数
        int leftDepth = root.left!= null? minDepth(root.left) : Integer.MAX_VALUE;
        // 计算右子树的最小深度，如果右子节点为空，则赋值为最大整数
        int rightDepth = root.right!= null? minDepth(root.right) : Integer.MAX_VALUE;
        // 返回左右子树中的最小深度加上根节点的深度 1
        return Math.min(leftDepth, rightDepth) + 1;
    }

    // 使用广度优先求解
    public static int minDepth1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        root.deep = 1;
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode curr = queue.poll();
            // 如果当前节点是叶子节点，返回其深度
            if (curr.left == null && curr.right == null) {
                return curr.deep;
            }
            if (curr.left!= null) {
                curr.left.deep = curr.deep + 1;
                queue.offer(curr.left);
            }
            if (curr.right!= null) {
                curr.right.deep = curr.deep + 1;
                queue.offer(curr.right);
            }
        }
        return 0;
    }

    /**
     * 二叉树节点类
     */
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        int deep;

        /**
         * 构造函数，初始化二叉树节点
         * @param val 节点值
         * @param left 左子节点
         * @param right 右子节点
         */
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}